import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Text7 {
    // 30.串联所有单词的子串
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ret = new ArrayList<>();

        Map<String,Integer> hash1 = new HashMap<String,Integer>();//保存字典中的单词频次
        for (String a : words)
            hash1.put(a,hash1.getOrDefault(a,0) + 1);

        int n = words[0].length(), m = words.length;
        //执行次数循环
        for (int i = 0; i < n; i++){
            int count = 0;
            Map<String,Integer> hash2 = new HashMap<String,Integer>();
            for (int left = i, right = i; n + right <= s.length(); right += n) {
                //进窗口 + 更新count
                String in = s.substring(right,right + n);
                hash2.put(in,hash2.getOrDefault(in,0) + 1);
                if (hash2.get(in) <= hash1.getOrDefault(in,0))
                    count++;
                //判断
                if (right - left + 1 > m * n){
                    String out = s.substring(left , left + n);
                    if (hash2.get(out) <= hash1.getOrDefault(out,0))
                        count--;
                    hash2.put(out,hash2.get(out) - 1);
                    left += n;
                }
                if (count == m)
                    ret.add(left);
            }
        }
        return ret;
    }
}
